package class15;

/**
 * <a href="https://leetcode.cn/problems/number-of-provinces/">547. 省份数量</a>
 */
public class Code01_FriendCircles {

    public int findCircleNum(int[][] isConnected) {
        UnionFind unionFind = new UnionFind(isConnected.length);
        for (int i = 0; i < isConnected.length; ++i) {
            for (int j = i + 1; j < isConnected[i].length; ++j) {
                if (isConnected[i][j] == 0) {
                    continue;
                }
                unionFind.union(i, j);
            }
        }
        return unionFind.setSize;
    }

    private static class UnionFind {
        int[] parent;
        int[] nodeSize;
        int[] stack;
        int setSize;

        UnionFind(int n) {
            parent = new int[n];
            nodeSize = new int[n];
            stack = new int[n];
            setSize = n;
            for (int i = 0; i < n; ++i) {
                parent[i] = i;
                nodeSize[i] = 1;
            }
        }

        int find(int i) {
            int hi = 0;
            while (i != parent[i]) {
                stack[hi++] = i;
                i = parent[i];
            }
            for (hi--; hi >= 0; hi--) {
                parent[stack[hi]] = i;
            }
            return i;
        }

        void union(int a, int b) {
            int aH = find(a);
            int bH = find(b);
            if (aH == bH) {
                return;
            }
            if (nodeSize[aH] > nodeSize[bH]) {
                nodeSize[aH] += nodeSize[bH];
                parent[bH] = aH;
            } else {
                nodeSize[bH] += nodeSize[aH];
                parent[aH] = bH;
            }
            setSize--;
        }
    }

}